package algorithm.tree;

import algorithm.Node;
import ch.qos.logback.core.encoder.LayoutWrappingEncoder;

/**
 * 两个节点最低公共祖先
 *
 * @author csp 2021-12-18
 */
public class Code04_LowestCommonAncestor {

    /**
     * 三种情况
     * 1、o1，o2在同一节点上，o1在o2上
     * 2、o2在o1上
     * 3、o1，o2在不同的树上
     *
     * 递归的方式，找子树要答案
     *
     *
     *
     *
     */
    public static Node lowestAncestor(Node head, Node o1, Node o2) {
        if (head == null || head == o1 || head == o2) {
            return head;
        }
        Node left = lowestAncestor(head.left, o1, o2);
        Node right = lowestAncestor(head.right, o1, o2);
        if (left != null && right != null) {
            return head;
        }
        //左右有两颗树，并不都有返回值
        return left != null ? left : right;
    }

    // 中序节点后继节点


}
